package my.algorithms.mcorrea.topcoder;

/**
 * A group of people stand before you arranged in rows and columns. Looking from
 * above, they form an R by C rectangle of people. You will be given a String[]
 * people containing the height of each person. Elements of people correspond to
 * rows in the rectangle. Each element contains a space-delimited list of
 * integers representing the heights of the people in that row. Your job is to
 * return 2 specific heights in a int[]. The first is computed by finding the
 * shortest person in each row, and then finding the tallest person among them
 * (the "tallest-of-the-shortest"). The second is computed by finding the
 * tallest person in each column, and then finding the shortest person among
 * them (the "shortest-of-the-tallest").
 *
 * @author mcorrea
 */
public class TallPeople {

	public static void main(String args[]) {
		String[] people = {"9 2 3", "4 8 7"};
		getPeople(people);

		String[] people1 = {"1 2",
			"4 5",
			"3 6"};
		getPeople(people1);

		String[] people2 = {"1 1",
			"1 1"};
		getPeople(people2);
		
		String[] people3 = 	{"1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20", "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20", "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20", "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20", "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20", "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20", "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20", "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20", "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20", "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20", "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20"}	;
		getPeople(people3);
		

	}

	public static void getPeople(String[] people) {
		int[] heights = new int[2];
		//find the tallest of shortest people
		int tallestShortest = 0;
		for (String r : people) {
			String[] row = r.split("\\s");
			//find the shortest for each row
			int shortest = Integer.parseInt(row[0]);
			for (int i = 1; i < row.length; i++) {
				if (Integer.parseInt(row[i]) < shortest) {
					shortest = Integer.parseInt(row[i]);
				}
			}
			if (shortest > tallestShortest) {
				tallestShortest = shortest;
			}
		}

		//find the shortest of tallest people
		int shortestTallest = Integer.MAX_VALUE;
		int n = people[0].split("\\s").length;
		for (int k = 0; k < n; k++) {
			int tallest = 0;
			for (String r : people) {
				String[] row = r.split("\\s");
				if (Integer.parseInt(row[k]) > tallest) {
					tallest = Integer.parseInt(row[k]);
				}
			}
			if (tallest < shortestTallest) {
				shortestTallest = tallest;
			}
		}


		System.out.println(tallestShortest);
		System.out.println(shortestTallest);

	}
}
